﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 博客素材
// 
// 原题连接：https://leetcode.cn/problems/majority-element/
// 题目描述：
/*
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3

示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
*/

// 方法1——暴力法(但会超出时间)
/*
思路：
对于每个元素，我们都向它的后面遍历，找到与它相同的元素，用一个变量count保存，若count大于⌊ n/2 ⌋则直接返回；
因为是要找到出现次数大于⌊ n/2 ⌋，所以当我们遍历到⌊ n/2 ⌋ + 1个元素时，就不用再往后找了，因为就算⌊ n/2 ⌋ + 2
个元素是第一次出现的，那即使它后面的元素都与它相等，那他出现的次数也不可能大于⌊ n/2 ⌋。
故外层循环我们只需要执行⌊ n/2 ⌋ + 1次。
*/
int majorityElement1(int* nums, int numsSize) {
	assert(nums);
	int N = numsSize / 2;
	int i = 0;
	int j = 0;
	for (i = 0; i < N + 1; i++) {
		int count = 1;
		for (j = i + 1; j < numsSize; j++) {
			if (nums[j] == nums[i]) {
				count++;
			}
		}
		if (count > N) {
			break;
		}
	}
	return nums[i];
}

// 方法2——排序
/*
思路：
如果将数组中的元素按升序或降序的顺序排序，那么下下标为⌊ n/2 ⌋
(数组的下标从0开始，那么下标为⌊ n/2 ⌋相当于第⌊ n/2 ⌋ + 1个元素)的
元素就一定是出现次数超过⌊ n/2 ⌋的元素，因为在排序后相同的元素一定是紧挨在一起的，
因为那一串出现次数大于⌊ n/2 ⌋的元素的长度一定大于数组长度的一半，所以不管那一串是排在
开头、中间、还是末尾。都会把下标⌊ n/2 ⌋给占了
*/
int majorityElement2(int* nums, int numsSize) {
	assert(nums);
	// 用冒泡排序先对数组进行排序
	int i = 0;
	int j = 0;
	for (i = 0; i < numsSize - 1; i++) {
		int flag = 1;
		for (j = 0; j < numsSize - 1 - i; j++) {
			if (nums[j] > nums[j + 1]) {
				int temp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = temp;
				flag = 0;
			}
		}
		if (flag) {
			break;
		}
	}
	return nums[numsSize / 2];
}

// 方法3——一对一打擂台
/*
思路：
我们可以先假设有这样一个擂台赛：
有若干个队在争抢一块“令牌”，比赛开始先把令牌交给第一个上台的人，
若下一个上台的人是自己队的就可以留在台上一起守护“令牌”，若不是，就只能一对一打，但最后都同归于尽。
“令牌”交给下一个上台的人。
最后留在台上手持“令牌”人是哪一队的，哪一队就获胜。
显而易见，一定是人数最多的那一队获胜。

这个方法扩展到数组中就是：
我们可以吧每个元素的数组的不同把它们分成不同的队伍，上台的顺序就是遍历数组的顺序。
用一个变量token来表示令牌，用一个变量count来表示在台上的某一队的人数。当下一个上台的元素与台上的是同一队时，
count++，否则count--，当count=0时，就将令牌交给下一个要遍历到的元素。
*/

int majorityElement3(int* nums, int numsSize) {
	int token = nums[0]; // 先把令牌给第一个上台的人
	int i = 0;
	int count = 0; // 统计台上的一共有多少个某队的人
	for (i = 0; i < numsSize; i++) {
		if (nums[i] == token) {
			count++;
		}
		else {
			count--;
			if (count == 0) {
				token = nums[i + 1];
			}
		}
	}
	return token;
}

// 方法4——分治法
/*
思路：
如果a是数组nums的众数，那如果我们将nums分成两部分，那么a一定至少是一部分的众数。
那我们分别求出这两部分各自的众数，再将这两个众数进行比较，如果这两个众数不同，那就看看哪个众数在其区间内出现的频次更高，
更高的那个就是整个区间的众数，如果这两个众数相同，则默认返回任意一个都行。
然后对左右区间也是用同样的方法，
一直递归下去就行了。
*/

// 我们现在来定义获取区间内众数频率的函数
int get_count(int num, int* left, int* right) {
	assert(left && right);
	int count = 0; // 记录频数
	while (left <= right) {
		if (*left == num) {
			count++;
		}
		left++;
	}
	return count;
}
// 首先定义一个递归返回众数的函数
// lo指向一个区间的起始地址，hi区间的结尾地址
int get_mode(int* lo, int* hi) {
	if ( hi - lo == 0 ) {
		return *lo; // 说明只有一个元素，直接返回lo[0]
	}
	// 拆分成更小的区间

	int mid = (hi - lo) / 2 ; // 获得区间中点
	int left = get_mode(lo, lo + mid); // 获得左区间的众数
	int right = get_mode(lo + mid + 1, hi); // 获得右区间的众数

	// 对两个区间的众数进行比较
	if (left == right) {
		return left;
	}
	else if (left == -1) {
		return right;
	}
	else if (right == -1) {
		return left;
	}

	// 不相等就要统计整个区间内左右众数出现的频数
	int left_count = get_count(left, lo, hi); // 统计区间内left出现的频数
	int right_count = get_count(right, lo, hi); // 统计区间内right出现的频数
	if (left_count > right_count) {
		return left;
	}
	else if (left_count < right_count) {
		return right;
	}
	else {
		return -1;
	}
}

// 这样我们只需要在函数里调用一次get_mode即可
int majorityElement4(int* nums, int numsSize) {
	return get_mode(nums, nums + numsSize - 1);
}


int main() {
	int arr[] = { 10, 9, 9, 9, 10 };
	int len = sizeof(arr) / sizeof(arr[0]);
	printf("%d", majorityElement4(arr, len));
	/*int* p1 = &arr[0];
	int* p2 = &arr[0];
	printf("%d", p2 - p1);*/

	return 0;
}